#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const pair<int, string> valueSymbols[] = {
    {1000, "M"},
    {900,  "CM"},
    {500,  "D"},
    {400,  "CD"},
    {100,  "C"},
    {90,   "XC"},
    {50,   "L"},
    {40,   "XL"},
    {10,   "X"},
    {9,    "IX"},
    {5,    "V"},
    {4,    "IV"},
    {1,    "I"},
};
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 1);

        for (int i = 1; i < n; ++i)
        {
            for (int j = 0; j < i; ++j)
            {
                if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        return *max_element(dp.begin(), dp.end());
    }

    string intToRoman(int num) {
        string res;
        for (const auto& [k, v] : valueSymbols)
        {
            while (num >= k)
            {
                num -= k;
                res += v;
            }
            if (num == 0) break;
        }
        return res;
    }

    int timeRequiredToBuy(vector<int>& tickets, int k) {
        int res = 0, tk = tickets[k];
        for (int i = 0; i < tickets.size(); ++i)
        {
            res += min(tickets[i], tk - (i > k));
        }
        return res;
    }
};